#
# @lc app=leetcode.cn id=611 lang=python3
#
# [611] 有效三角形的个数
#
from typing import List

"""
三角形的边长遵循 [任意两边之和大于第三边] 的原则，且当 0 <= a <= b <= c 时，可以推出当最短的两边之和大于最长边时，这三条边可以组成三角形
将数组进行排序，倒序进行遍历，来枚举三角形最长边，在最长边的左侧区间寻找符合的两条边
所以本题就转换为了类似 三数之和 的问题，用最长边作为 target ，去寻找另外两条短边

优化部分也是相同的原理：
  1.如果最小的两条短边之和都大于最长边，则剩余的都将符合，所以为：C(k+1,3)=(k+1)*k*(k-1) // 6，计算完成后即可跳出循环
  2.如果最长的两条短边之和依然小于最长边，则证明该最长边不能与其他边组成三角形，所以跳过本次循环，寻找较小的最长边
"""


# @lc code=start
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        res = 0

        for i in range(n-1, 1, -1):
            x = nums[i]

            if nums[0] + nums[1] > x:
                res += (i+1) * i *(i-1) // 6
                break

            if nums[i-1] + nums[i-2] <= x: continue

            j = 0
            k = i - 1
            while j < k:
                s = nums[j] + nums[k]
                if s > x:                    
                    res += k-j
                    k -= 1                  
                else:
                    j += 1

        return res
# @lc code=end

res = Solution.triangleNumber(Solution, [2,2,3,4])
print(res)
